package com.cat.chapter049;

/**
 * @author cat
 * @description https://leetcode.cn/problems/minimum-window-substring/
 * @create 2025/7/18 20:49
 * @since JDK17
 */

public class Solution03 {
    public String minWindow(String str, String ttr) {
        char[] s = str.toCharArray(), t = ttr.toCharArray();
        int len = 0, n = s.length, start = 0, debt = t.length;
        int[] cnt = new int[128];   // 欠债表
        for (int i = 0; i < t.length; i++) {
            cnt[t[i]]--;    //
        }

        for (int r = 0, l = 0; r < n; r++) {
            if (cnt[s[r]]++ < 0) { // 还了一个
                debt--;
            }
            if (debt == 0) {    // 还完债务了
                while (cnt[s[l]] > 0) { //
                    cnt[s[l++]]--;
                }
                if (len < r - l + 1) {
                    len = r - l + 1;
                    start = l;
                }
            }
        }

        return str.substring(start, len);
    }
}
